#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <mpi.h>

#define N_PAL 1000000
#define TAM_PAL 5

// vetor de palavras a serem geradas.. é declarado globalmente para evitar estouro de pilha
char palavras[N_PAL][TAM_PAL+1];

// A função BinarySearch recebe uma cadeia de caracteres key e
// um vetor array[low,high] de cadeias de caracteres cujos
// elementos estão em ordem lexicográfica (ordem de dicionário).
// A função devolve um índice de um elemento de array que seja
// igual a key. Se tal índice não existe, a função devolve
// -1.

int BinarySearch(char* key, char array[N_PAL][TAM_PAL+1], int low, int high)
{
   int mid, cmp;

   if (low > high)
    return -1;

   mid = (low + high) / 2;

   cmp = strcmp(key, array[mid]);

   if (cmp == 0 )
      return mid;
   else if (cmp < 0)
      return BinarySearch( key, array, low, mid - 1);
   else
      return BinarySearch( key, array, mid + 1, high);
}

int main(int argc, char* argv[])
{
	FILE *arq, *aux;
	char c;
	char palavra[50], aleatoria[TAM_PAL+1], p1[TAM_PAL], p2[TAM_PAL], node[MPI_MAX_PROCESSOR_NAME];
	char **menores;
	int tam_pal, i, j, k, x, y, ctd, tam, partes, partes_inteiras, resto, pos, idx, idx2, linhas=0, encontradas=0, rank, n_processos, nameSize, achou=0, mpi_flag=0;
	int contador[TAM_PAL] = {0,0,0,0,0};

	MPI_Init(&argc, &argv);

	MPI_Comm_rank(MPI_COMM_WORLD,&rank);
        MPI_Comm_size(MPI_COMM_WORLD,&n_processos);
        MPI_Get_processor_name(node,&nameSize);
        MPI_Status status;
	MPI_Request reqs;

	if(!(arq = fopen("palavras.txt", "r")))
	{
	    printf("ERRO: Problema ao abrir o arquivo.");
	    MPI_Abort(MPI_COMM_WORLD, -1);
	}

	idx=0;
	pos=0;
	while((c = fgetc(arq)) != EOF)
	{
	    if((c != ',') && (c != '\n') && (c != ' ') && (c != '-')) // as palavras são separadas por { ',' ; '\n' ; ' ' ; '-' }
		    palavra[idx++] = c;
	    else //final de palavra
	    {
		    palavra[idx] = '\0';
		    idx=0;
		    tam = strlen(palavra);
		    if(tam > 0) // garante que não vai pegar espaço em branco, para o caso em que há vírgula seguida de espaço, por exemplo
		    {
			if(pos==0) // primeira palavra a ser inserida
			{
			    if(tam<=5) // palavra com tamanho menor ou igual a 5 é inserida diretamente
			    {
			        strcpy(palavras[pos], palavra);
			        contador[tam-1] += 1;
			        ++pos;
			    }
			    else // palavras maiores do que 5 são quebradas em palavras menores
			    {
			        partes = tam/5;
			        resto = tam%5;

			        if(resto != 0) // adiciona uma parte para as letras restantes
			            partes += 1;
			        
			        menores = (char**)malloc(partes*sizeof(char*));
			        for(i=0; i<partes; ++i)
			            menores[i] = (char*)malloc((TAM_PAL+1)*sizeof(char));

			        for(i=0; i<partes; ++i) // divide a palavra entre as partes menores
			        {
			            for(j=0; j<TAM_PAL; ++j)
			            {
			                menores[i][j] = palavra[i*TAM_PAL+j];
			            }
			            menores[i][j] = '\0';
			        }

			        strcpy(palavras[pos], menores[0]); // copia a primeira parte
			        contador[TAM_PAL-1] += 1;
			        ++pos;

			        for(i=1; i<partes; ++i) // copia as outras partes
			        {
				    for(k=0; (strcmp(menores[i], palavras[k]) > 0) && k<pos; ++k); // encontra a posição para inserir a palavra no vetor
			            if (strcmp(menores[i], palavras[k]) != 0) // evita a inserção de palavras repetidas
			            {
			                //if(k<pos)
			                    //memmove(palavras+k+1, palavras+k, (N_PAL-k-1)*(TAM_PAL+1));
					for(j=pos; j>k; --j)
                                            strcpy(palavras[j], palavras[j-1]);
			                strcpy(palavras[k], menores[i]);
			                contador[strlen(menores[i])-1] += 1;
			                ++pos;
			            }


			        }

			        for(i=0; i<partes; ++i)
			            free(menores[i]);
			        free(menores);

			    }
			}

			else // demais palavras
			{
			    if(tam<=5) // palavra com tamanho menor ou igual a 5 é inserida diretamente
			    {
				for(k=0; (strcmp(palavra, palavras[k]) > 0) && k<pos; ++k); // encontra a posição para inserir a palavra no vetor
			        if(strcmp(palavra, palavras[k]) != 0) // evita a inserção de palavras repetidas
			        {
			            //if(k<pos)
			                    //memmove(palavras+k+1, palavras+k, (N_PAL-k-1)*(TAM_PAL+1));
				    for(j=pos; j>k; --j)
                                            strcpy(palavras[j], palavras[j-1]);
			            strcpy(palavras[k], palavra);
			            contador[strlen(palavra)-1] += 1;
			            ++pos;
			        }
			    }
			    else // palavras maiores do que 5 são quebradas em palavras menores
			    {
			        partes = tam/5;
			        resto = tam%5;

			        if(resto != 0) // adiciona uma parte para as letras restantes
			            partes += 1;
			        
			        menores = (char**)malloc(partes*sizeof(char*));
			        for(i=0; i<partes; ++i)
			            menores[i] = (char*)malloc((TAM_PAL+1)*sizeof(char));

			        for(i=0; i<partes; ++i) // divide a palavra entre as partes menores
			        {
			            for(j=0; j<TAM_PAL; ++j)
			            {
			                menores[i][j] = palavra[i*TAM_PAL+j];
			            }
			            menores[i][j] = '\0';
			        }

			        for(i=0; i<partes; ++i)
			        {
				    for(k=0; (strcmp(menores[i], palavras[k]) > 0) && k<pos; ++k); // encontra a posição para inserir a palavra no vetor
			            if(strcmp(menores[i], palavras[k]) != 0) // evita a inserção de palavras repetidas
			            {
			                //if(k<pos)
			                    //memmove(palavras+k+1, palavras+k, (N_PAL-k-1)*(TAM_PAL+1));
					for(j=pos; j>k; --j)
                                            strcpy(palavras[j], palavras[j-1]);
			                strcpy(palavras[k], menores[i]);
			                contador[strlen(menores[i])-1] += 1;
			                ++pos;
			            }
			        }

			        for(i=0; i<partes; ++i)
			            free(menores[i]);
			        free(menores);
			    }
			}
		    }
	    }
	}

	printf("\nVetor contador no rank %d: ", rank);
	for(i=0; i<TAM_PAL; ++i)
		printf("%d ", contador[i]);
	printf("\n");

	printf("\n\nPalavras lidas no rank %d:\n", rank);
	for(i=0; i<pos; ++i)
	{
		printf("%d: %s\n", i, palavras[i]);
	}
	
	srandom(time(NULL));

	tam = pos;
	printf("\nTotal de palavras a serem geradas: %d\n", pos);

	//for(i=0; i<5; ++i) // gera as palavras por ordem de tamanho
	//{
		//ctd = contador[i];
		
		while(tam > 0)
		{
			    for(j=0; j < n_processos; ++j)
			    {
				if(j != rank)
				{
					MPI_Iprobe(j,1,MPI_COMM_WORLD,&mpi_flag,&status); // verifica se há mensagem para ser recebida
					
					if (mpi_flag == 1)
					{
						MPI_Irecv(&idx2, 1, MPI_INT, j, 1, MPI_COMM_WORLD, &reqs);
						mpi_flag = 0;
						for(k=idx2; k<tam-1; ++k)
                       					strcpy(palavras[k], palavras[k+1]);
						//memmove(palavras+idx2, palavras+idx2+1, (N_PAL-j-1)*(TAM_PAL+1));
						tam--;
						//ctd -= 1;
						encontradas++;
					}
				}
			    }
				
			    tam_pal = (random()%5)+1;

		    	    for(j=0; j<tam_pal+1; ++j) // gera palavras aleatórias
				aleatoria[j] = (char)(random()%26)+97;
			    aleatoria[j] = '\0';

			    idx = BinarySearch(aleatoria, palavras, 0, tam-1); // procura a palavra no vetor
			    
			    if(idx != -1) // caso a palavra esteja no vetor ela é retirada e os outros processos são informados
			    {
				//memmove(palavras+idx, palavras+idx+1, (N_PAL-j-1)*(TAM_PAL+1));
				for(k=idx; k<tam-1; ++k)
                       			strcpy(palavras[k], palavras[k+1]);
				tam--;
				//ctd -= 1;
				encontradas++;
				printf("Palavra gerada no processo %d (host %s): %s - %d encontradas\n", rank, node, aleatoria, encontradas);
				for(j=0; j < n_processos; ++j)
				{
					if(j != rank)
					{
						MPI_Isend(&idx, 1, MPI_INT, j, 1, MPI_COMM_WORLD, &reqs);
					}
				}
			    }
			    
		   

		}
	//}
	
	fclose(arq);

	MPI_Finalize();

	return 0;
}
